
// This MAC version is converted from an earlier standalone
// version of AC3 algo's developed for IJCAI-01 paper:
// Making AC3 optimal.
// 14 Feb 2004

// The O(ed) space method to implement AC3.1 is added
// on 15 Feb 2004 

/* 
   initialization of 'support' is move from ac3_init() to CSP_Ac3()
*/

#include "mac3.h"
#include <errno.h>

FilterQueue::FilterQueue(int n1) : n(n1), length(n1+1)
{
  int i, j;

  // we have only n^2+1 slots in the Q. 
  // Each constraint can occupy one and only one
  // slot in the Q. so we need another
  // array to record the status of each constraint.

  // Q = (Qentry  *) malloc( sizeof( Qentry) * length );
  Q = new Qentry [length];
  if (!Q){
    printf (" Mem error Q\n");
    exit(-1);
  }
  head = tail = 0;
  
  int *statusp;
  
  // status is to prevent a constraint enter queue twice
  // status = (int *) malloc (sizeof(int) * length );
  status = new int [length];
  if (!status){
    printf (" Mem error (status)\n");
    exit(-1);
  }
  // enable all positions in the Q 
  for(i = 0, statusp = status; i < n; i++){
    *statusp = 0;
    statusp++;
  }
}

FilterQueue::~FilterQueue()
{
  if (Q != NULL) delete [] Q; 
  if (status != NULL) delete [] status;
  // free(Q);
  // free(status);
}

void FilterQueue::enqueue(int i)
{
  if ( !status[i] ){ // not entered before?
    status[i] = 1; // disable (i,j) to enter Q before (i,j) is dequeued
    Q[tail].i = i;
    tail = (tail + 1) % length ;
  }
}

void FilterQueue::dequeue(int &i)
{
  i = Q[head].i;
  head = (head + 1) % length;
  status[i] = 0; // enable (i,j) 
}

// return false if csp is found not satisfied otherwise true

bool CSP_Ac3::ac3_init(FilterQueue& Q)
{
  int i, j;

  // check all constraints first time

  for(i = 0; i < n; i++)
    for(cllp = cross_link_list[i].begin();
	cllp != cross_link_list[i].end(); ++cllp){
      j = *cllp;
      if (REVISE3(i,j)){
	if (empty_domain(i)) return false; 
	//enq_neighbours(i, j);
	Q.enqueue(i); 
      }
    }
  numOfRemovedValuesB4Propogation = num_removed_values;
  return true; //so far, the CSP is Arc-consistent
}

// return false if csp is found not satisfied otherwise true
// this function establishes the data to remember of 
// the last support. 
bool CSP_Ac3::ac3_1_init(FilterQueue& Q) 
{
  int i, j;
  bool acConsistent = true;
  
  //----------------- allocate memory for support ------------
  // decrease the size of support, which improves the efficiency of REVISEnew1
  // support = (Support *) malloc( sizeof(Support)*(n*n));
  support = new Support [n*n];
  if (!support){
    printf (" Mem error (support) %d n=%d\n", errno, n);
    exit(-1);
  }

  // allocate memory for support wrt each constraint

  for(i = 0; i < n; i++)
    for(cllp = cross_link_list[i].begin();
	cllp != cross_link_list[i].end(); ++cllp){
      j = *cllp;
      // support[i*n + j] = (Support) malloc( sizeof(int)*d );
      support[i*n + j] = (Support) new int [d];
      if (!support[i*n+j]){
	printf (" Mem error (support) %d n=%d\n", errno, n);
	exit(-1);
      }     
    }
  
  //----------------- populate support[] and check AC of the csp--
  // check all constraints first time
  for(i = 0; i < n; i++)
    for(cllp = cross_link_list[i].begin();
	cllp != cross_link_list[i].end(); ++cllp){
      j = *cllp;
      if (REVISE3_1_init(i,j)){
	if (empty_domain(i)) {
	  acConsistent = false; 
	  goto cleanup;
	}
	Q.enqueue(i); 
      }
    }
 cleanup:
  numOfRemovedValuesB4Propogation = num_removed_values;
  return acConsistent; //so far, the CSP is Arc-consistent
}

CSP_Ac3::CSP_Ac3(int n1, int d1, int e1, int T, int *S, float threshold) : CSP(n1, d1, e1, T, S)
{
  initCSP_Ac3();
}

CSP_Ac3::CSP_Ac3(int n1, int d1, int e1, float threshold) : CSP(n1, d1, e1)
{
  initCSP_Ac3();
}

CSP_Ac3::CSP_Ac3(char *directory, float threshold) : CSP(directory)
{
  initCSP_Ac3();
}

void CSP_Ac3::initCSP_Ac3(){
  support = NULL; 
  firstRevision = NULL;
  stopValues = NULL; 
  numOfRemovedValuesB4Propogation = -1;
}

// if ac3 is used, nothing is done in this destruction
CSP_Ac3::~CSP_Ac3()
{
  int i, j;
  
  // printf("&support=%x when its destroyed", support);
  if( support != NULL) { // AC3.1 is used (mac3_1 is used)
    for(i=0; i < n; i++)
      for(cllp = cross_link_list[i].begin();
	  cllp != cross_link_list[i].end(); ++cllp){
	j = *cllp;
	if(support[i*n + j] != NULL) delete [] support[i*n+j];
      }
    
    delete [] support; 
  }

  // these are for mac3.1.1
  if( firstRevision != NULL) delete [] firstRevision; 
  if( stopValues != NULL) delete [] stopValues;
}

//consistency is enforced on arc (i,j)
bool CSP_Ac3::REVISE3(int i, int j)
{
  int x, y;  

  Domain *dip, *djp;
  bool DELETE, viable;

  DELETE = false; // no value is removed
  dip = domainOfVar(i); // domain + i*(d+1);
  djp = domainOfVar(j); // domain + j*(d+1);

  // curij: the matrix of relation (i,j)

  // printf ("\nchecking (%d,%d):", i, j );
  for(x = dip[0].next, curij = cn[i*n + j] + (x-1)*d; 
      x != 0; x = dip[x].next, curij = cn[i*n + j] + (x-1)*d){
    viable = false;
    // printf("%d ", x);
    for( y = djp[0].next; y != 0; y = djp[y].next){
      num_checks++;
      if (curij[y-1]) {
	viable = true;
	break;
      }
    }
    if (!viable){ // no support
      remove(i,x);
      DELETE = true; // some value in x is removed
    }
  } // all values in i
  return DELETE;
}

// THe new instance of AC-3 will employ REVISEnew1
// in its initialization phase and REVISEnew2 in
// propagation phase.

// The reason to use a seperate
// This REVISE is used only in the initialization of ac3_1
// to initialize support[i,a,j].
bool CSP_Ac3::REVISE3_1_init(int i, int j)
{
  int x, y;
  Domain *dip, *djp;
  Support sp;
  bool DELETE, viable;

  DELETE = false; // no value is removed
  dip = domainOfVar(i); //domain + i*(d+1);
  djp = domainOfVar(j); //domain + j*(d+1);
  // v2: move sp out from the following for loop
  sp = support[i*n + j] ;

  // curij: the matrix of relation (i,j)

  // printf ("\nchecking (%d,%d):", i, j );
  // note: curij(x,y) means (x+1, y+1) satisfy constraint (i,j)
  // the first element in domain of i is 1 rather than 0.
  // the content of sp[i,j,x-1] is y(from 1 to d)

  // v2: move curij into for control statement
  for(x = dip[0].next, curij = cn[i*n + j] + (x-1)*d; 
      x != 0; x = dip[x].next, curij = cn[i*n + j] + (x-1)*d){
    viable = false;
    // printf("%d ", x);
    for( y = djp[0].next; y != 0; y = djp[y].next){
      num_checks++;
      if (curij[y-1]) {
	viable = true;
	sp[x-1] = y;
	break;
      }
    }
    if (!viable){
      remove(i,x);
      DELETE = true; // some value in x is removed
    }
  } // all values in i
  return DELETE;
}
// This REVISE is used in the propogation phase (of ac3_1) and mac3_1.
bool CSP_Ac3::REVISE3_1_propogate(int i, int j)
{
  int x, y;
  Domain *dip, *djp;
  Support sp;
  BackupedSupport backupedSupport;
  int DELETE, viable;

  extern int curInstance;

  DELETE = false; // no value is removed
  dip = domainOfVar(i); // domain + i*(d+1);
  djp = domainOfVar(j); // domain + j*(d+1);

  // curij: the matrix of relation (i,j)
  // std::cout << "i=" << i << " j=" << j << " x=" << x << '\n';
  //  if( (x > 30) || (x <= 0)) 
  //    std::cout << "x=" << x << " is spoiled\n"; 
  //  if ((y == 30) || (y == 0)){
  //    std::cout << "support is spoiled\n"; 
  //    std::cout << "i=" << i << " j=" << j << " x=" << x << " y=" << y << '\n';
  //  }

  // printf ("\nchecking (%d,%d):", i, j );
  for(x = dip[0].next, sp = support[i*n + j] ; 
      x != 0; x = dip[x].next){
    curij = cn[i*n + j] + (x-1)*d;
    // printf("%d ", x);
 
    y = sp[x-1];
    if (! djp[y].yes){ // is the support of x no longer valid?
      viable = false;
      for( y = djp[y].next; y != 0; y = djp[y].next){
	num_checks++;
	if ((djp[y].yes) && (curij[y-1])) { //if y is valid 
	  viable = true;
	  //--------------------backup the old support--------------
	  
	  backupedSupport.varI = i;
	  backupedSupport.varJ = j;
	  backupedSupport.value = x;
	  backupedSupport.support = sp[x-1]; 
	  if( sp[x-1] == 0) 
	    cout << "its already spoiled before backup: \n";
	  backupedSupport.phase = curPhase; // curPhase defined in class CSP
	  previousSupports.push(backupedSupport); 
	  //-------------------- end of backup ---------------------
	  sp[x-1] = y; // remember this support
	  break;
	}
      }
      if (!viable){ // no support
	remove(i,x);
	DELETE = true; // some value in x is removed
      }
    } // else x is supported
    else num_checks++;
  } // all values in i
  return DELETE; 
}

// traditional implementation of AC-3

bool CSP_Ac3::ac3()
{
  int i, j;
  FilterQueue Q(n); 
  
  if (!ac3_init(Q)) return false;
  
  return ac3_propogate(Q); 
}

bool CSP_Ac3::ac3_propogate(FilterQueue& Q) {

  // variables i and j
  int i, j;

  // std::cout << "removed value is %d \npropagation is on ...", num_removed_values);
  while ( !Q.empty()){
    Q.dequeue(j);

    for(cllp = cross_link_list[j].begin();
	cllp != cross_link_list[j].end(); ++cllp){
      i = *cllp;

      if (isAssigned(i)) continue; // var i being instantiated, ommit it

      if (REVISE3(i,j)){
	if (empty_domain(i)) return false;

	//enq_neighbours(i, j);
	Q.enqueue(i);
      } // the domain of i is revised
    } // all neigbouring variables of var j
  } // propogate all the vars in Q

  return true;
}

bool CSP_Ac3::ac3_1()
{
  int i, j;
  FilterQueue Q(n);
  
  if (!ac3_1_init(Q)) return false;
  
  return ac3_1_propogate(Q);
}

bool CSP_Ac3::ac3_1_propogate(FilterQueue& Q) {

  // variables i, j
  int i, j;
  // std::cout << "removed value is" << num_removed_values 
  //	    << "\npropagation is on ...";
  while (! Q.empty()){
    Q.dequeue(j);
    
    for(cllp = cross_link_list[j].begin();
	cllp != cross_link_list[j].end(); ++cllp){
      i = *cllp;

      if (isAssigned(i)) continue; // var i being instantiated, ommit it

      if (REVISE3_1_propogate(i,j)){
	if (empty_domain(i)) return false;

	//enq_neighbours(i, j);
	Q.enqueue(i);
      }
    } // end for loop: handle all neighbours of j
  } // end while
  return true;
}

bool CSP_Ac3::ac3_1_1()
{
  int i, j;
  FilterQueue Q(n);
 
  // initialization of firstRevision.
  // this could be maintained in backtracking. but given
  // the small number of constraints, we just set true 
  // for every entry in the domain at the begining of 
  // mac3.1.1
  firstRevision = new bool [n*n]; 
  stopValues = new int [n*n*d];
  
  // the first step is exactly the same as ac3_1. 
  if (!ac3_1_init(Q)) return false;
  
  return ac3_1_1_propogate(Q);
}

bool CSP_Ac3::ac3_1_1_propogate(FilterQueue& Q) {

  // variables i, j
  int i, j;

  // A new round of propogation. 
  // We set firstRevision to be true. 
  for(int i = 0; i < n; i++)
    for(cllp = cross_link_list[i].begin();
	cllp != cross_link_list[i].end(); ++cllp){
      j = *cllp;
      firstRevision[i*n+j] = true;
    }

  // std::cout << "removed value is" << num_removed_values 
  //	    << "\npropagation is on ...";
  while (! Q.empty()){
    Q.dequeue(j);
    
    for(cllp = cross_link_list[j].begin();
	cllp != cross_link_list[j].end(); ++cllp){
      i = *cllp;

      if (isAssigned(i)) continue; // var i being instantiated, ommit it

      if (REVISE3_1_1(i,j)){
	if (empty_domain(i)) return false;

	//enq_neighbours(i, j);
	Q.enqueue(i);
      }
    } // end for loop: handle all neighbours of j
  } // end while
  return true;
}

//mac3 is called after assigning a value to variable
bool CSP_Ac3::mac3(int var, int value){
  FilterQueue Q(n);
  Domain* dp;
  int dummyValue = headOfDomain();

  dp = domainOfVar(var); 
  for(int curP = dp[0].next; curP != dummyValue;  curP = dp[curP].next){
    if(curP != value) // remove all values except 'value'
      remove(var, curP); 
  }

  Q.enqueue(var); 
  return ac3_propogate(Q); 
}

bool CSP_Ac3::mac3(int var){
	 FilterQueue Q(n);
	 Q.enqueue(var);
	 return ac3_propogate(Q);
}

// mac3_1 is called after assigning a value to a variable.
bool CSP_Ac3::mac3_1(int var, int value){
  FilterQueue Q(n);
  Domain* dp;
  int dummyValue = headOfDomain();


  dp = domainOfVar(var); 
  for(int curP = dp[0].next; curP != dummyValue;  curP = dp[curP].next){
    if(curP != value) // remove all values except 'value'
      remove(var, curP); 
  }

  Q.enqueue(var); 
  return ac3_1_propogate(Q); 
}

bool CSP_Ac3::mac3_1(int var){
	 FilterQueue Q(n);
	 Q.enqueue(var);
	 return ac3_1_propogate(Q);
}

// restore support list for AC3.1
// just before (not including) the 'phase'. 'before' is smaller here.
void CSP_Ac3::restoreMAC3_1(int phase) {

  BackupedSupport backuped;
  
  while (!previousSupports.empty()) {
    backuped = previousSupports.top(); 
    if (backuped.phase < phase) break; // no more states to restore 
    (support[backuped.varI*n + backuped.varJ])[backuped.value-1] = backuped.support;
    previousSupports.pop();
  }
}

// mac3_1 is called after assigning a value to a variable.
bool CSP_Ac3::mac3_1_1(int var, int value){
  FilterQueue Q(n);
  Domain* dp;
  int dummyValue = headOfDomain();
  int j;

  dp = domainOfVar(var); 
  for(int curP = dp[0].next; curP != dummyValue;  curP = dp[curP].next){
    if(curP != value) // remove all values except 'value'
      remove(var, curP); 
  }

  Q.enqueue(var); 
  return ac3_1_1_propogate(Q); 
}

bool CSP_Ac3::mac3_1_1(int var){
	 FilterQueue Q(n);
	 Q.enqueue(var);
	 return ac3_1_1_propogate(Q);
}

bool CSP_Ac3::REVISE3_1_1(int i, int j)
{
  int x, y, stopValue; 
  Domain *dip, *djp;
  Support sp;
  int DELETE, viable, indexBase;

  extern int curInstance;

  DELETE = false; // no value is removed
  dip = domainOfVar(i); // domain + i*(d+1);
  djp = domainOfVar(j); // domain + j*(d+1);
  indexBase = i*n*d + j*d; 

  // curij: the matrix of relation (i,j)
  // std::cout << "i=" << i << " j=" << j << " x=" << x << '\n';
  //  if( (x > 30) || (x <= 0)) 
  //    std::cout << "x=" << x << " is spoiled\n"; 
  //  if ((y == 30) || (y == 0)){
  //    std::cout << "support is spoiled\n"; 
  //    std::cout << "i=" << i << " j=" << j << " x=" << x << " y=" << y << '\n';
  //  }

  // printf ("\nchecking (%d,%d):", i, j );
  for(x = dip[0].next, sp = support[i*n + j] ; 
      x != 0; x = dip[x].next){
    curij = cn[i*n + j] + (x-1)*d;
    // printf("%d ", x);
   
    viable = false; 

    if (firstRevision[i*n + j]){
      // There are many choices here.
      // 1. let y=0, we start from scratch. this is good
      //    if the domain size is small. but worst case
      //    of the algorithm would be O(ed^2)!
      // 2. We start from y, dp[y].next,  ... until
      //    find the first value avail in the domain, 
      //    and then search a support starting from that value
      //    but we do this only once at the start of the assignment a new value to
      //    the current var after the previous assignment fails. 
      //    PROBLEM: the stop value found in this way is not safe becos
      //             later, this value may be removed. 
      //    SOLUTION: we just set y=0
      //    
      ///     A time stamp mechanism 
      //      is necessary for this. In this case we only 
      //      need to backup the revised variables and their
      //      time stamp (the phase). 
      // we use 2 without further time stamp. 

      // following the .next field of a deleted value, we can either 
      // reach a value in CURRENT domain or 0;
      y = sp[x-1]; // normally sp[x-1] is just a previous support
      if(djp[y].yes) {
	stopValues[indexBase + x-1] = djp[y].pre;
	viable = true; 
      }
      else {
	// find the first value, avail in current domain, after y 
	for ( y = djp[y].next; y != 0; y = djp[y].next)
	  if ( djp[y].yes) break; 
	
	// now y is eigther a valid value of D_y or 0
	// the stop value should be the previous one of y
	stopValues[indexBase + x-1] = djp[y].pre; 

	// find the first support after y 
	stopValue = stopValues[indexBase + x-1]; // eigther a value in the domain or 0    
	
	for( y=djp[stopValue].next; y != stopValue; y = djp[y].next){
	  if (y == 0) continue; // We have to skip the dummy value 0
	  num_checks++;
	  if (curij[y-1]) { //if y is support
	    viable = true;
	    sp[x-1] = y; // remember this support
	    break;
	  }
	} // end of for loop on y of domain j, trying to find a support for x
 	if(!viable) {// We havn't checked stopValue yet
	  if (stopValue != 0)
	    if ((djp[stopValue].yes) && (curij[stopValue-1])) { //if y is valid 
	      viable = true;
	      sp[x-1] = stopValue; // remember this support
	    }
	}
     } // end of the case when sp[x-1] is no longer a valid domain value
    } // end of the first revision of arc (i,j)
    else { 
      y = sp[x-1]; // second time to revise (i,j), so let y be the previous support

      if (djp[y].yes) viable = true;  // the support of x is still valid
      else{
	stopValue = stopValues[indexBase + x-1]; // eigther a value in the domain or 0    

	if (stopValue != y) { // there is more value in the domain  
	  bool noSupport = false;
	  if (stopValue != 0) { // in this case the stored stopValue may be removed
	    if (!djp[stopValue].yes) { // stopValue has been removed!
	      bool supportB4StopValue = (y < stopValue);
	      // So we need to find a new stopValue in the current domain.
	      // Here we make use of a property of function remove() and the structure
	      // of Domain that following .pre field of a value, we can always find 
	      // a valid value before the value of concern, and we arrive at 0.
	      for(stopValue = djp[stopValue].pre; stopValue != 0; stopValue = djp[stopValue].pre)
		if (djp[stopValue].yes) break; // find a stop value in current domain
	      // now stopValue is either 0 or a value in current domain
	      if ((supportB4StopValue) && (stopValue < y))
		noSupport = true;
	      else
		stopValues[indexBase + x-1] = stopValue;
	    } // reset the backuped stopValue
	  }
	
	  if( !noSupport) { // try to find a support
	    // y is currently not valid, we need to find the next valid value in 
	    // domain of var j. its again a bit tricky here:
	    // y might not be a valid value in the domain
	    // but stopValue is now either 0 or a valid value.
	    // So, we have to be very careful trying to compare them using != .
	    for( y = djp[y].next; y != stopValue; y = djp[y].next){
	      if (y == 0) continue; // We have to skip the dummy value 0
	      num_checks++;
	      if ((djp[y].yes) && (curij[y-1])) { //if y is valid 
		viable = true;
		sp[x-1] = y; // remember this support
		break;
	      }
	    } // end for loop on y 
	    
	    if(!viable) {// We havn't checked stopValue yet
	      if (stopValue != 0)
		if ((djp[stopValue].yes) && (curij[stopValue-1])) { //if y is valid 
		  viable = true;
		  sp[x-1] = stopValue; // remember this support
		}
	    }
	  } // otherwise no support
	} // otherwise no more support
      }// end of handling djp[y].yes = false
    } //end of the non-first revision of arc (i,j)
     
    if (!viable){ // no support for x
      remove(i,x);
      DELETE = true; // some value in x is removed
    }
  } // for loop on value x in domain of var i
  
  firstRevision[i*n + j] = false;
  return DELETE; 
}

void CSP_Ac3::statistics(){

  std::cout << "# of values removed before search:" << "# of values removed:" 
	    << "# of constraint checks" << '\n';
  std::cout << numOfRemovedValuesB4Propogation << ':' << num_removed_values << ':'
	    << num_checks << '\n'; 
  // << ':' << ACConsistent  
}
